{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 作业"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using matplotlib backend: Qt5Agg\n"
     ]
    }
   ],
   "source": [
    "%matplotlib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 冒泡排序法"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< .mine
   "execution_count": 4,
||||||| .r47
   "execution_count": 147,
=======
   "execution_count": 5,
>>>>>>> .r52
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\animation.py:971: UserWarning: MovieWriter imagemagick unavailable\n",
      "  warnings.warn(\"MovieWriter %s unavailable\" % writer)\n"
     ]
    },
    {
     "ename": "OSError",
     "evalue": "Error saving animation to file (cause: [Errno 22] Invalid argument) Stdout: b'' StdError: b''. It may help to re-run with --verbose-debug.",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mOSError\u001b[0m                                   Traceback (most recent call last)",
      "\u001b[1;32mC:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\animation.py\u001b[0m in \u001b[0;36mgrab_frame\u001b[1;34m(self, **savefig_kwargs)\u001b[0m\n\u001b[0;32m    290\u001b[0m             self.fig.savefig(self._frame_sink(), format=self.frame_format,\n\u001b[1;32m--> 291\u001b[1;33m                              dpi=self.dpi, **savefig_kwargs)\n\u001b[0m\u001b[0;32m    292\u001b[0m         \u001b[1;32mexcept\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mRuntimeError\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mIOError\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\figure.py\u001b[0m in \u001b[0;36msavefig\u001b[1;34m(self, *args, **kwargs)\u001b[0m\n\u001b[0;32m   1571\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 1572\u001b[1;33m         \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcanvas\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mprint_figure\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m   1573\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\backends\\backend_qt5agg.py\u001b[0m in \u001b[0;36mprint_figure\u001b[1;34m(self, *args, **kwargs)\u001b[0m\n\u001b[0;32m    221\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mprint_figure\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 222\u001b[1;33m         \u001b[0mFigureCanvasAgg\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mprint_figure\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    223\u001b[0m         \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdraw\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\backend_bases.py\u001b[0m in \u001b[0;36mprint_figure\u001b[1;34m(self, filename, dpi, facecolor, edgecolor, orientation, format, **kwargs)\u001b[0m\n\u001b[0;32m   2243\u001b[0m                 \u001b[0mbbox_inches_restore\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0m_bbox_inches_restore\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 2244\u001b[1;33m                 **kwargs)\n\u001b[0m\u001b[0;32m   2245\u001b[0m         \u001b[1;32mfinally\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\backends\\backend_agg.py\u001b[0m in \u001b[0;36mprint_raw\u001b[1;34m(self, filename_or_obj, *args, **kwargs)\u001b[0m\n\u001b[0;32m    536\u001b[0m         \u001b[1;32mtry\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 537\u001b[1;33m             \u001b[0mfileobj\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mwrite\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mrenderer\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_renderer\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mbuffer_rgba\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    538\u001b[0m         \u001b[1;32mfinally\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mOSError\u001b[0m: [Errno 22] Invalid argument",
      "\nDuring handling of the above exception, another exception occurred:\n",
      "\u001b[1;31mOSError\u001b[0m                                   Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-4-75f925dcf49e>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     43\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     44\u001b[0m \u001b[0mani\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0manimation\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mFuncAnimation\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfig\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mupdate\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mgenerator\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0minterval\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;36m300\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mrepeat\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mFalse\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 45\u001b[1;33m \u001b[0mani\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msave\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"anim2.gif\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mwriter\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;34m\"imagemagick\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     46\u001b[0m \u001b[1;31m# plt.show()\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\animation.py\u001b[0m in \u001b[0;36msave\u001b[1;34m(self, filename, writer, fps, dpi, codec, bitrate, extra_args, metadata, extra_anim, savefig_kwargs)\u001b[0m\n\u001b[0;32m   1011\u001b[0m                         \u001b[1;31m# TODO: See if turning off blit is really necessary\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1012\u001b[0m                         \u001b[0manim\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_draw_next_frame\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0md\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mblit\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;32mFalse\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 1013\u001b[1;33m                     \u001b[0mwriter\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mgrab_frame\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m**\u001b[0m\u001b[0msavefig_kwargs\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m   1014\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1015\u001b[0m         \u001b[1;31m# Reconnect signal for first draw if necessary\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\ProgramData\\Anaconda3\\lib\\site-packages\\matplotlib\\animation.py\u001b[0m in \u001b[0;36mgrab_frame\u001b[1;34m(self, **savefig_kwargs)\u001b[0m\n\u001b[0;32m    297\u001b[0m             raise IOError('Error saving animation to file (cause: {0}) '\n\u001b[0;32m    298\u001b[0m                           \u001b[1;34m'Stdout: {1} StdError: {2}. It may help to re-run '\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 299\u001b[1;33m                           'with --verbose-debug.'.format(e, out, err))\n\u001b[0m\u001b[0;32m    300\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    301\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0m_frame_sink\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mOSError\u001b[0m: Error saving animation to file (cause: [Errno 22] Invalid argument) Stdout: b'' StdError: b''. It may help to re-run with --verbose-debug."
     ]
    }
   ],
   "source": [
    "import matplotlib.animation as animation\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "def generator():\n",
    "    for i in range(1,len(arr)+1):\n",
    "        for j in range(0,len(arr)-i):\n",
    "            if arr[j]>arr[j+1]:\n",
    "                lines[j].set_color('r')\n",
    "                lines2[j].set_color('r')\n",
    "                lines[j+1].set_color('y')\n",
    "                lines2[j+1].set_color('y')\n",
    "                arr[j],arr[j+1]=arr[j+1],arr[j]\n",
    "                yield arr\n",
    "            else:\n",
    "                lines[j].set_color('r')\n",
    "                lines2[j].set_color('r')\n",
    "                lines[j + 1].set_color('y')\n",
    "                lines2[j + 1].set_color('y')\n",
    "                yield arr\n",
    "        lines[len(arr)-i].set_color('b')\n",
    "        lines2[len(arr)-i].set_color('b')\n",
    "        yield arr\n",
    "\n",
    "\n",
    "def update(datag):\n",
    "    for i in range(len(datag)):\n",
    "        lines[i].set_ydata([0, datag[i]])\n",
    "        lines2[i].set_ydata([0, datag[i]])\n",
    "\n",
    "    return lines\n",
    "\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "arr = [15, 8, 10, 9, 6, 4, 16, 5, 13, 26, 18, 2, 45, 34, 23, 1, 7, 3]\n",
    "n = len(arr)\n",
    "xdata = [[i+1 for i in range(n)], [i+1 for i in range(n)]]\n",
    "ydata = [[0 for i in range(n)], arr]\n",
    "\n",
    "ax.set_xticks([i+1 for i in range(n)])\n",
    "lines = ax.plot(xdata, ydata, linewidth=2, color='r')\n",
    "lines2 = ax.plot(xdata, ydata, 'ro', markersize=4)\n",
    "\n",
    "ani = animation.FuncAnimation(fig, update, generator, interval=300,repeat=False)\n",
    "# ani.save(\"anim2.gif\", writer=\"imagemagick\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 快速排序法"
   ]
  },
  {
   "cell_type": "code",
<<<<<<< .mine
   "execution_count": 3,
||||||| .r47
   "execution_count": 135,
=======
   "execution_count": 6,
>>>>>>> .r52
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.animation as animation\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "def quick_sort(num, l, r):\n",
    "    if l >= r:\n",
    "        if l >= len(lines):\n",
    "            l = len(lines) - 1\n",
    "        if r >= len(lines):\n",
    "            r = len(lines) - 1\n",
    "        lines[l].set_color('b')\n",
    "        lines2[l].set_color('b')\n",
    "        lines[r].set_color('b')\n",
    "        lines2[r].set_color('b')\n",
    "        yield num\n",
    "        return\n",
    "    flag = l\n",
    "\n",
    "    for i in range(l + 1, r + 1):\n",
    "        if num[flag] > num[i]:\n",
    "            tmp = num[i]\n",
    "            for j in range(i, flag, -1):\n",
    "                num[j] = num[j - 1]\n",
    "            num[flag] = tmp\n",
    "            lines[flag].set_color('r')\n",
    "            lines2[flag].set_color('r')\n",
    "            lines[flag+1].set_color('y')\n",
    "            lines2[flag+1].set_color('y')\n",
    "            flag += 1\n",
    "            yield num\n",
    "    yield num\n",
    "\n",
    "    for m in quick_sort(num, l, flag - 1):\n",
    "        yield m\n",
    "    lines[flag].set_color('b')\n",
    "    lines2[flag].set_color('b')\n",
    "    for n in quick_sort(num, flag + 1, r):\n",
    "        yield n\n",
    "\n",
    "\n",
    "def update(data_gen):\n",
    "    for i in range(len(data_gen)):\n",
    "        lines[i].set_ydata([0, data_gen[i]])\n",
    "        lines2[i].set_ydata([0, data_gen[i]])\n",
    "\n",
    "    return lines\n",
    "\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "arr = [12, 8, 10, 9, 6, 4, 16, 5, 13, 26, 18, 2, 45, 34, 23, 1, 17, 3]\n",
    "n = len(arr)\n",
    "\n",
    "xdata = [[i + 1 for i in range(n)], [i + 1 for i in range(n)]]\n",
    "ydata = [[0 for i in range(n)], arr]\n",
    "\n",
    "ax.set_xticks([i + 1 for i in range(n)])\n",
    "lines = ax.plot(xdata, ydata, linewidth=2, color='r')\n",
    "lines2 = ax.plot(xdata, ydata, 'ro', markersize=4)\n",
    "\n",
    "ani = animation.FuncAnimation(fig, update, quick_sort(arr, 0, len(arr) - 1), interval=300, repeat=False)\n",
    "plt.show()\n",
    "# ani.save(\"anim3.gif\", writer=\"imagemagick\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3.0
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}